алгоритмическая неразрешимость
- алгоритмическая неразрешимость
АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ — важнейшее свойство некоторых классов корректно поставленных задач, допускающих применение алгоритмов. Оно состит в том, что задачи каждого из этих классов в принципе не имеют какого-либо общего, универсального алгоритма решения, объединяющего этот класс. Несмотря на полную однотипность условий и требований, здесь, как ни парадоксально, принципиально невозможна однотипность метода решения. А. н. не означает неразрешимости тех или иных единичных проблем данного класса — часть из них может иметь свои решения. Но в целом данный класс задач не имеет ни общего универсального алгоритма решения, ни ветвящегося алгоритма полного разбиения класса на подклассы, к каждому из которых был бы применим свой специфический алгоритм.
Алгоритмически неразрешимыми являются, напр., проблема распознавания: закончит ли свою работу (остановится ли) или же «зависнет» в бесконечном цикле произвольно выбранная программа действий алгоритмического типа (не только компьютерная, но и реализуемая человеком по алгоритмическому типу); проблема эквивалентности программ (нет универсального алгоритма, позволяющего установить эту эквивалентность); проблема тождества двух математических выражений; проблема распознавания того, можно ли из имеющихся автоматов собрать заданный автомат; а также множество других проблем, относящихся к топологии, к теории групп и к другим областям.
А. н. как невозможность обобщенной системы точных предписаний по решению задач одного и того же типа имеет принципиальное значение для психологии мышления, обучения и теории познания. В частности, из нее вытекает, что основные компоненты деятельности человека (планирование, выполнение, контроль результатов, коррекция) не могут быть построены на алгоритмической основе, хотя и могут включать в качестве вспомогательных те или иные алгоритмические процедуры. Решение задачи, относящейся к типу алгоритмически неразрешимых, с неизбежностью включает неалгоритмизуемые компоненты и требует творчества: способ ее решения не выводится из более общего известного типового метода, а изобретается. Успех здесь не может быть гарантирован на 100% никакими методами (в отличие от ситуации с алгоритмически разрешимыми задачами).
Таким образом, А. н. как объективная невозможность универсальных точных предписаний, однозначно приводящих к заданному результату, означает свободу выбора и объективную необходимость творческого поиска.
А.Н. Поддьяков
Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация».
И.Т. Касавин.
2009.
Полезное
Смотреть что такое "алгоритмическая неразрешимость" в других словарях:
Алгоритмическая неразрешимость — в математической логике свойство математической задачи, заключающееся в отсутствии алгоритма ее решения. См. также: Алгоритмы Логика Финансовый словарь Финам … Финансовый словарь
АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ — (англ. algorithmic unsolvability) важнейшее свойство некоторых классов корректно поставленных задач, допускающих применение алгоритмов, состоящее в том, что задачи каждого из этих классов в принципе не имеют к. л. общего, универсального алгоритма … Большая психологическая энциклопедия
Алгоритмическая неразрешимость — … Википедия
НЕРАЗРЕШИМОСТЬ — невозможность решения данной задачи точно очерченными средствами. Ниже рассмотрены важнейшие примеры Н. в математике. Алгоритмическая неразрешимость. В различных областях математики возникают проблемы, в к рых требуется найти единую механич.… … Математическая энциклопедия
АЛГОРИТМИЧЕСКАЯ ПРОБЛЕМА — проблема, в к рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении… … Математическая энциклопедия
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ — одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, что неразрешимость (и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, а путем сведения к исследуемой проблеме такой … Математическая энциклопедия
Теория алгоритмов — Теория алгоритмов наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач,… … Википедия
Алгоритмически неразрешимая задача — В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой… … Википедия
РАЗРЕШЕНИЯ ПРОБЛЕМА — РАЗРЕШЕНИЯ ПРОБЛЕМА возникла в связи с осознанием невозможности провести некоторые построения дозволенными методами. Первыми примерами неразрешимых задач явились решение в радикалах уравнений выше четвертой степени и невозможность провести… … Философская энциклопедия
ЛОГИКА В РОССИИ — эволюция современной (математической) логики в России. Кон. 19 в. и нач. 20 в. знаменуют выход логики за рамки силлогистики и появление логиков новаторов, таких как П.С. Порецкий, М.В. Каринский, Л.В. Рутковский, СИ. Поварнин, и др. Казанский… … Философская энциклопедия